\documentclass[12pt, a4paper,english,spanish]{article}
\usepackage{babel}
%\parindent = 10 pt
%\parskip = 11 pt
\usepackage[width=15.5cm, left=3cm, top=2.5cm, height= 24.5cm]{geometry}
\usepackage{amsmath}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{graphicx}
\usepackage{verbatim}
\usepackage[latin1]{inputenc}
\usepackage{tikz}
\usepackage{pgfplots}

\begin{document}
\renewcommand{\refname}{} 

\begin{center}
\large{\textbf{M\'etodos Num\'ericos}}

\normalsize{Primer Cuatrimestre de 2012}

\vspace{2mm}

Departamento de Computaci\'on\\
Facultad de Ciencias Exactas y Naturales\\
Universidad de Buenos Aires\\

\vspace{10mm}

\LARGE{\textsc{\textbf{Trabajo Pr\'actico 3}}} \\

\LARGE{Redistribuidor vehicular antis\'ismico}\\  

\vspace{10mm}

\normalsize

\begin{tabular}{c|c}
\hline
\textbf{Autor} & \textbf{Correo electr\'onico} \\
\hline
Marina A. Niikado & mariniik@yahoo.com.ar\\
Ezequiel Schwab & ezequiel.schwab@gmail.com\\
Franco Pistasoli & fpistasoli@gmail.com\\
\hline
\end{tabular}

\end{center}

\vskip 12pt
\rule{\textwidth}{1.2pt}
\vskip 5pt

\section*{Resumen}
En el presente trabajo se proponen diferentes m\'etodos para reubicar veh\'iculos en un edificio de varios pisos, evitando que \'este colapse cuando ocurra el terremoto. Para esto, las frecuencias naturales de los pisos tienen que tener valores lejanos a la frecuencia del sismo (valor conocido). 
Al modificar la distribuci\'on de los autos en el edificio, las frecuencias de cada piso tambi\'en cambian. De esta manera, mediante un plan de reubicaci\'on correcto, se logra una buena estabilidad del edificio durante el terremoto. 
Se analizan las ventajas y desventajas de los algoritmos propuestos para la nueva distribuci\'on de veh\'iculos. 
Se encontraron m\'etodos eficientes en cuanto a cantidad de movimientos de autos, pero al mismo tiempo, costosos en cuanto a tiempo de ejecuci\'on. Se propone, entonces, un nuevo algoritmo que sea bastante m\'as r\'apido, pero a costa de verse levemente incrementada la cantidad de movimientos de autos.
  

\section*{Palabras clave}
\textsc{Autovalores, factorizaci\'on QR, algoritmo QR, frecuencias naturales.}
 
\newpage

\tableofcontents

\newpage

\section{Introducci\'on te\'orica}
El objetivo de este trabajo es evaluar la estabilidad de un edificio frente a un posible terremoto.   
Este edificio de varios pisos funciona como estacionamiento, teniendo una cierta cantidad de autos livianos y pesados en cada piso. Entre cada piso existe una fuerza F de restituci\'on. Se aplica la segunda ley de Newton a cada secci\'on y se obtiene un sistema de ecuaciones. A partir de este sistema escrito en forma matricial, se llega a tener una matriz A, de la cual nos interesan sus autovalores para poder obtener las frecuencias naturales de los pisos. Para evitar que el edificio colapse, ninguna de estas frecuencias puede tener valores cercanos a la frecuencia del sismo. 
Para el c\'alculo de los autovalores, se utiliz\'o el algoritmo QR, encontrando previamente, mediante el m\'etodo de Givens, la factorizaci\'on QR de la matriz A.


\subsection*{Factorizaci\'on QR(Rotaciones de Givens)} \cite{UniZ}
Para toda matriz A, existe Q matriz ortogonal y R matriz triangular superior, tal que A $=$ QR. 
Es posible hallar la factorizaci\'on QR de A, mediante rotaciones de Givens. \\

Dada una matriz A$_0$ $=$ A, se busca una secuencia de matrices ortogonales W$_1$, W$_2$, ...W$_k$ tales que la matriz A$_i$ $=$ W$_i$ A$_i$$_-$$_1$ tenga m\'as elementos nulos debajo de la diagonal que A$_i$$_-$$_1$ para i$=$1,...,k, de forma que la matriz R $=$ A$_k$ final es triangular superior, llegando a la siguiente expresi\'on: \\
W$_k$W$_k$$_-$$_1$...W$_1$A $=$ R, resultando A $=$ QR, con Q $=$ W$_1$$^t$W$_2$$^t$...W$_k$$^t$ ortogonal y R triangular superior. Es decir, la concatenaci\'on de todas las rotaciones de Givens realizadas, forman la matriz ortogonal Q. \\
Este m\'etodo es \'util para matrices tipo esparsas, donde s\'olo pocos elementos fuera de la diagonal necesitan ser anulados.



\subsection*{Algoritmo QR}\cite{Burden} 
Mediante el algoritmo QR podemos calcular los autovalores de una matriz A. \\
El m\'etodo QR forma una sucesi\'on de las matrices A $=$ A$^($$^1$$^)$, A$^($$^2$$^)$, A$^($$^3$$^)$, ...:
A$^($$^1$$^)$ $=$ A se factoriza como un producto A$^($$^1$$^)$ = Q$^($$^1$$^)$R$^($$^1$$^)$, donde Q$^($$^1$$^)$ es ortogonal y R$^($$^1$$^)$ triangular superior.
A$^($$^2$$^)$ se define como A$^($$^2$$^)$ $=$ R$^($$^1$$^)$Q$^($$^1$$^)$.
A$^($$^1$$^)$ se factoriza como un producto A$^($$^i$$^)$ $=$ Q$^($$^i$$^)$R$^($$^i$$^)$ de una matriz ortogonal Q$^($$^i$$^)$ y de una matriz tirangular superior R$^($$^i$$^)$. 
Despu\'es definimos A$^($ $^i$ $^+$ $^1$$^)$ como el producto de R$^($$^i$$^)$ y Q$^($$^i$$^)$ en la direcci\'on inversa A$^($ $^i$ $^+$ $^1$$^)$ $=$ R$^($$^i$$^)$Q$^($$^i$$^)$. 
Dado que Q$^($$^i$$^)$ es ortogonal, R$^($$^i$$^)$ $=$ Q$^($$^i$$^)$$^t$A$^($$^i$$^)$ y A$^($ $^i$ $^+$ $^1$$^)$ $=$ R$^($$^i$$^)$Q$^($$^i$$^)$ $=$ Q$^($$^i$$^)$$^t$A$^($$^i$$^)$)Q$^($$^i$$^)$ $=$ Q$^($$^i$$^)$$^t$A$^($$^i$$^)$Q$^($$^i$$^)$. 
A$^($ $^i$ $^+$ $^1$$^)$ tiende a una matriz triangular superior, la cual tiene los mismos valores caracter\'isticos que la matriz original A. 
Los autovalores de A son los elementos contenidos en la diagonal de A$^($ $^i$ $^+$ $^1$$^)$.  


\newpage


\section{Desarrollo}  

El principal objetivo de este trabajo ha sido el de evitar que un edificio, con una determinada distribuci\'on de veh\'iculos y pisos, colapse cuando llegue el impacto de un terremoto de frecuencia 3Hz. Para lograr esto, se debi\'o dise\~nar al menos dos algoritmos que lograran reubicar los autos del edificio en otros pisos, de manera tal que luego de la reubicaci\'on, el edificio no colapsara al llegar el terremoto. 

\subsection*{Planteo del problema}
Garantizar que un edificio de $n$ pisos no colapse es equivalente a aplicar un algoritmo de reubicaci\'on de veh\'iculos para lograr que todas las frecuencias naturales de cada piso (de ahora en m\'as, las ra\'ices cuadradas de los opuestos de los autovalores de una matriz $A$) se encuentren fuera del rango $(2,7;3,3)$. Por lo tanto, nuestro primer paso consisti\'o en hallar esta matriz $A$ para poder hallarle sus autovalores.

Como se puede observar en la secci\'on Ap\'endice A, la matriz que buscamos est\'a definida de la siguiente manera: $A = M^{-1} K$, donde $M \in {\mathbb{R}}^{n \times n}$ es una matriz diagonal con las masas de los pisos, y $K\in\mathbb{R}^{n\times n}$ es una matriz tridiagonal. Luego de reacomodar los t\'erminos del sistema de ecuaciones diferenciales ordinarias (ver nuevamente el Ap\'endice A), nos queda lo siguiente:

\begin{eqnarray*}
m_1 \ddot{x}_1 & = & -(k_0+k_1) x_1 + k_1 x_2 \nonumber \\
m_2 \ddot{x}_2 & = & k_1 x_1 - (k_1+k_2)x_2 + k_2 x_3 \nonumber \\
m_3 \ddot{x}_3 & = & k_2 x_2 - (k_2+k_3)x_3 + k_3 x_4 \nonumber \\
\vdots &  & \vdots \nonumber \\
m_n \ddot{x}_n & = & -k_{n-1} x_n + k_{n-1} x_{n-1}  \nonumber \\
\end{eqnarray*}

Luego, este sistema es equivalente a resolver $M \ddot{x} = K x$, donde entonces 

\[
 M =
 \begin{pmatrix}
  m_1 & 0 & \cdots & 0 \\
  0 & m_2 & \cdots & 0 \\
  \vdots  & \vdots  & \ddots & \vdots  \\
  0 & 0 & \cdots & m_n
 \end{pmatrix}
\]

y 

\[
 K =
 \begin{pmatrix}
  -(k_0+k_1) & k_1 & 0 & 0 & \cdots & 0 \\
  k_1 & -(k_1+k_2) & k_2 & 0 & \cdots & 0 \\
  0 & k_2 & -(k_2+k_3) & k_3 & \cdots & 0 \\  
  \vdots  & \vdots  & \ddots & \ddots & \ddots & \vdots  \\
  0 & \cdots & 0 & 0 & k_{n-1} & -k_{n-1} \\
 \end{pmatrix}
\]

Por lo tanto, como $M$ es diagonal, y los elementos de su diagonal son todos distintos de cero, $M$ tiene inversa, y

\[
 M^{-1} =
 \begin{pmatrix}
  \frac{1}{m_1} & 0 & \cdots & 0 \\
  0 & \frac{1}{m_2} & \cdots & 0 \\
  \vdots  & \vdots  & \ddots & \vdots  \\
  0 & 0 & \cdots & \frac{1}{m_n}
 \end{pmatrix}
\]

De esta manera, conseguimos la matriz $A$ haciendo $M^{-1} K$. 

Nuestro segundo paso fue aplicarle el algoritmo QR a esta matriz $A$. Dentro de este algoritmo, lo primero que se hace es encontrar la factorizaci\'on QR de $A$ (la cual sabemos que existe para cualquier matriz). Para hallar esta factorizaci\'on, usamos el m\'etodo de Givens, pues $A$ es tridiagonal y a medida que se incrementa su tama\~no, se incrementa la proporci\'on de 0's en la matriz (como sabemos, Givens es conveniente cuando tenemos matrices esparsas, es decir, como muchos elementos nulos).

Un error que cometimos al iniciar el c\'odigo del algoritmo QR fue que supusimos que la matriz $A$ era sim\'etrica, y por lo tanto, luego de una cantidad de iteraciones, se encontrar\'ia una matriz diagonal que contendr\'ia a los autovalores de $A$ en la diagonal. Luego, como criterio de parada hab\'iamos puesto que el algoritmo terminara cuando se est\'a tendiendo a una matriz diagonal. Sin embargo, $A$ no es necesariamente sim\'etrica, y en este caso el algoritmo QR tiende a una matriz triangular superior. Entonces, nuestro nuevo criterio de parada pas\'o a ser \'este: el algoritmo termina una vez que la norma 1 del vector formado por los valores del tri\'angulo inferior de la matriz $A_k$ (el elemento $k$-\'esimo en la sucesi\'on de matrices que genera el algoritmo QR) tiende a 0.  

Luego de aplicarle el algoritmo QR a $A$, se obtienen sus autovalores (negativos). Para encontrar las frecuencias naturales del sistema, se toma la ra\'iz cuadrada de los opuestos de los autovalores. Es decir, si $\lambda_1,\dots,\lambda_n$ son los autovalores de $A$, entonces los valores $\omega_i=\sqrt{-\lambda_i}$, para $i=1,\dots,n$, son las frecuencias naturales de cada piso. Si alguna de estas frecuencias est\'a en el rango $(2,7;3,3)$, entonces se aplica nuevamente el algoritmo de reubicaci\'on y se vuelve a calcular la matriz $M^{-1}$, y se invoca al algoritmo QR nuevamente\footnote{La matriz $K$ no se vuelve a calcular, ya que contiene datos de los coeficientes de rigidez de los pisos, que son constantes.}. El proceso se repite mientras alguna de las frecuencias caiga en ese intervalo. Cuando se logra reubicar los veh\'iculos de forma tal que el edificio no colapse, termina la simulaci\'on y se devuelve el n\'umero de veh\'iculos que se reubicaron. 


\subsection*{Algoritmos de reubicaci\'on}

Los dos algoritmos que dise\~namos en primera instancia son ``Random'' e ``Intuici\'on''.


\subsubsection*{Algoritmo Intuici\'on}

La idea de este algoritmo es, una vez que determinamos cu\'al es el piso que est\'a en conflicto (va a a ser el piso del cual moveremos algun auto), buscar el piso destino m\'as resistente (es decir, aqu\'el cuya frecuencia natural est\'e lo m\'as alejada posible de 3.3). Este algoritmo lo elegimos, como bien dice su nombre, porque intu\'iamos en que nos pod\'ia dar una buena soluci\'on, adem\'as de que era f\'acil de implementar. Una vez implementado el algoritmo, nos dimos cuenta de que muchas veces ni siquiera nos daba una soluci\'on, y si encontraba alguna, no era la mejor como veremos mas adelante en la secci\'on de Experimentaci\'on.


\subsubsection*{Algoritmo Random}

Lo implementamos por la sencillez de hacer el algoritmo y porque no le *cre\'iamos* a nuestro algoritmo anterior de que algunos tests no tenian soluci\'on. El algoritmo lo que hace es b\'asicamente re-asignar todos  los autos a pisos al azar. Sab\'iamos que con este algoritmo no iba a ser el ideal, ya que las posibilidades de que nos de la soluci\'on \'optima (con \'optima queremos decir, menor cantidad de movimientos de autos) era muy baja, o dicho de otra forma, ten\'iamos que tener mucha suerte para que justo nuestro algoritmo haya elegido los valores al azar tal que minimizara la cantidad de movimientos de autos entre pisos.

\vspace{8 mm}

Como estos algoritmos no nos convenc\'ian, comenzamos a pensar alg\'un algoritmo que fuera m\'as exhaustivo (en el sentido de que analizara muchas posibles combinaciones y se quedara con la *mejor*) sin importar si \'este no era eficiente o f\'acil de implementar. De esta forma, llegamos a nuestro siguiente algoritmo ``Medalla''.

\subsubsection*{Algoritmo Medalla}

La idea de este algoritmo es, una vez que determinamos un piso que esta en conflicto, buscamos el movimiento de auto (sea pesado o liviano) que haga que la frecuencia del piso en conflicto se acerque lo mas posible a 3.3 o 2.7. Por ejemplo, supongamos un edificio de 3 pisos, cada uno con autos, y supongamos que el piso 2 nos da que tiene una frecuencia natural de 2.8, por lo tanto colapsa. Las frecuencias obtenidas del piso 2, una vez realizados los distintos movimientos de autos supongamos que nos dan:

\vspace{8 mm}

\begin{tabular}{|l |r |}
\hline
Movimiento & Frecuencia\\
\hline
1 a 2 & 2.81\\
\hline
1 a 3  & 2.83 \\
\hline
2 a 1 & 2.77\\
\hline
2 a 3 & 2.84\\
\hline
3 a 1 & 2.76\\
\hline
3 a 2 &  2.90\\
\hline
\end{tabular}

\vspace{8 mm}

Entonces, en este caso,  el primer movimiento que realizar\'ia el algoritmo ser\'ia de 3 a 1, ya que es el que mas se acerca a 2.7.

\vspace{5 mm}

Para agilizar un poco este algoritmo (ya que para n grandes, al probar todas las posibles alternativas de movimiento de autos se vuelve muy lento) hicimos una leve mejora que no afect\'o los resultados del algoritmo. Esta leve mejora fue crear un vector de pisos ``obsoletos'' en los que nos guardamos los movimientos de autos en los que mover un auto nos alej\'o en vez de acercarnos a 3.3 o 2.7, dependiendo si la frecuencia del piso en conflicto era mayor (o igual) o menor que 3 respectivamente. Es decir, en el ejemplo anterior, ser\'ian movimientos obsoletos los movimientos 1 a 2, 1 a 3, 2 a 3 y 3 a 2 ya que en todos ellos nos alejamos de 2.7 con respecto a 2.8 (frecuencia del piso en conflicto). Por lo tanto, para esos movimientos ni siquiera calculamos la frecuencia que nos da despu\'es de la 1era iteracion. En el caso de que el piso que est\'abamos tratando de solucionar deja de estar en conflicto, pero surge otro piso diferente a estar en conflicto, entonces pisosObsoletos se ``limpia''. Ademas de los movimientos ya mencionados, pisosObsoletos siempre tiene como ``movimientos obsoletos'' a los movimientos que tienen como mismo piso destino a su piso origen (ejemplos, 1 a 1, 2 a 2 y 3 a 3 en el ejemplo anterior), evit\'andonos hacer calculos redundantes.

\vspace{8 mm}

Al ser el algoritmo anterior muy lento cuando n se hac\'ia cada vez m\'as grande (a\'un con la leve mejora para agilizarlo), buscamos una forma de agilizarlo, tratando de que no se incremente (o se incremente m\'inimamente) la cantidad de movimientos de autos. De este modo, analizamos los movimientos realizados por nuestro algoritmo Medalla, y vimos que los movimientos realizados generalmente se repet\'ian (es decir, si en una iteraci\'on se realizaba el movimiento de un auto del piso 2 al piso 3, y el piso en cuesti\'on segu\'ia estando en conflicto, entonces generalmente el movimiento en la iteraci\'on siguiente iba a ser el mismo movimiento que antes). De este modo, llegamos a nuestro algoritmo llamado ``Medalla Lazy''.

\subsubsection*{Algoritmo Medalla Lazy}

Este algoritmo es id\'entico al Medalla salvo por un cambio. En cada iteraci\'on, nos guardamos siempre el \'ultimo movimiento realizado. Si en el piso de origen del \'ultimo movimiento realizado sigue habiendo autos para mover (sean pesados o livianos segun corresponda con el movimiento realizado anteriormente), entonces se mueven autos directamente sin buscar otra combinaci\'on mejor posible hasta que no haya mas autos pesados o livianos (segun corresponda) para mover, o hasta que el piso que estaba en conflicto ya no lo este m\'as. Esta mejora hizo que se reduzca notablemente la velocidad del algoritmo anterior, pero nos trajo una leve suba en la cantidad de movimientos de autos realizados como veremos m\'as adelante en los distintos experimentos. Por este motivo (al dar valores diferentes) decidimos dejarlo como un algoritmo diferente, aunque haya sido s\'olo una version ``agilizada'' del algoritmo Medalla.

\subsubsection*{Algoritmo Random Optimizado}

Este \'ultimo algoritmo surgi\'o con la idea de mejorar la cantidad de movimientos de autos realizados en el algoritmo random. El procedimiento que realiza es llamar al algoritmo random, y luego, ir moviendo autos a sus pisos de or\'igenes hasta justo antes de que el edificio vuelva a colapsar. De este modo, reducimos la cantidad de movimientos que nos otorg\'o la distribuci\'on de autos del algoritmo random.

\vspace{5 mm}

Para la elecci\'on de los movimientos, miramos, para cada piso origen en el que haya mas autos de los que hab\'ia originalmente antes de llamar al algoritmo Random, todas las combinaciones posibles con los pisos destinos que tienen menos autos de los que ten\'ian originalmente, y nos quedamos con la combinaci\'on que logre que la frecuencia m\'as cercana a 2.7 (si es menor a 2.7) o 3.3 (si es mayor a 3.3) est\'e lo m\'as alejada posible.  Esta mejora igualmente no nos trajo una gran reducci\'on en el n\'umero de movimientos, como veremos m\'as adelante en los experimentos, dej\'andolo relegado en cuanto a cantidad de movimientos comparado con otros algoritmos, pero siendo \'este notablemente m\'as r\'apido en encontrar una soluci\'on al problema mientras m\'as grande sea la cantidad de pisos.

\pagebreak

\section{Resultados}

\subsection*{Experimento 1: Comparaci\'on de algoritmos determin\'isticos.}
Para este experimento se tomaron 5 archivos de prueba, donde cada uno se corresponde con un edificio de distinto n\'umero de pisos. Para cada caso analizamos la eficiencia de cada algoritmo determin\'istico (\texttt{algoritmoMedalla}, \texttt{algoritmoMedallaLazy} y \texttt{algoritmoIntuicion}), es decir, comparamos la cantidad de veh\'iculos que se deben reubicar en el edificio, para cada algoritmo, para que el edificio no colapse. 

\vspace{5 mm}
\textbf{(a)}
\begin{figure}[here]
\begin{center}
\begin{tikzpicture}
\begin{axis}[
 	width=7cm,
    height=7cm,
    symbolic x coords={Medalla,Medalla Lazy,Intuicion},
    x tick label style={font=\small,text width=1.5cm,align=center},
    xtick=data,
    ylabel=Movimientos,
    enlarge x limits=0.4,
    nodes near coords,
    ymin = 20,
bar width=30pt,
    ]
    \addplot[ybar,fill=green] coordinates {
        (Medalla,74)
        (Medalla Lazy,75)
        (Intuicion,76)
    };
\end{axis}
\end{tikzpicture}
\caption{Comparaci\'on de m\'etodos de reubicaci\'on determin\'isticos para \texttt{prueba3.txt}}
\label{determ3} 
\end{center}
\end{figure}

\vspace{5 mm}
\textbf{(b)}
\begin{figure}[here]
\begin{center}
\begin{tikzpicture}
\begin{axis}[
 	width=7cm,
    height=7cm,
    symbolic x coords={Medalla, Medalla Lazy},
    x tick label style={font=\small,text width=1.5cm,align=center},
    xtick=data,
    ylabel=Movimientos,
    enlarge x limits=1,
    nodes near coords,
    ymin = 20,
    bar width=30pt,
    ]
    \addplot[ybar,fill=green] coordinates {
        (Medalla,99)
        (Medalla Lazy,103)
    };
\end{axis}
\end{tikzpicture}
\caption{Comparaci\'on de m\'etodos de reubicaci\'on determin\'isticos para \texttt{prueba5.txt}}
\label{determ5} 
\end{center}
\end{figure}

\vspace{10 mm}
\textbf{(c)}
\begin{figure}[here]
\begin{center}
\begin{tikzpicture}
\begin{axis}[
 	width=7cm,
    height=7cm,
    symbolic x coords={Medalla, Medalla Lazy},
    x tick label style={font=\small,text width=1.5cm,align=center},
    xtick=data,
    ylabel=Movimientos,
    enlarge x limits=1,
    nodes near coords,
    ymin = 20,
    bar width=30pt,
    ]
    \addplot[ybar,fill=green] coordinates {
        (Medalla,59)
        (Medalla Lazy,60)
    };
\end{axis}
\end{tikzpicture}
\caption{Comparaci\'on de m\'etodos de reubicaci\'on determin\'isticos para \texttt{prueba6.txt}}
\label{determ6} 
\end{center}
\end{figure}

\vspace{5 mm}
\textbf{(d)}
\begin{figure}[here]
\begin{center}
\begin{tikzpicture}
\begin{axis}[
 	width=7cm,
    height=7cm,
    symbolic x coords={Medalla, Medalla Lazy},
    x tick label style={font=\small,text width=1.5cm,align=center},
    xtick=data,
    ylabel=Movimientos,
    enlarge x limits=1,
   nodes near coords,
    ymin = 10,
    bar width=30pt,
    ]
    \addplot[ybar,fill=green] coordinates {
        (Medalla,19)
        (Medalla Lazy,20)
    };
\end{axis}
\end{tikzpicture}
\caption{Comparaci\'on de m\'etodos de reubicaci\'on determin\'isticos para \texttt{prueba10.txt}}
\label{determ10} 
\end{center}
\end{figure}

\pagebreak
\textbf{(e)}
\begin{figure}[here]
\begin{center}
\begin{tikzpicture}
\begin{axis}[
 	width=7cm,
    height=7cm,
    symbolic x coords={Medalla, Medalla Lazy},
    x tick label style={font=\small,text width=1.5cm,align=center},
    xtick=data,
    ylabel=Movimientos,
    enlarge x limits=1,
    nodes near coords,
    ymin = 20,
    bar width=30pt,
    ]
    \addplot[ybar,fill=green] coordinates {
        (Medalla,55)
        (Medalla Lazy,61)
    };
\end{axis}
\end{tikzpicture}
\caption{Comparaci\'on de m\'etodos de reubicaci\'on determin\'isticos para \texttt{prueba20.txt}}
\label{determ20} 
\end{center}
\end{figure}



\subsection*{Experimento 2: Comparaci\'on de algoritmos no determin\'isticos.}

Para este experimento se tomaron los 4 archivos de prueba otorgados por la catedra, y estudiamos diferentes ejecuciones de los algoritmos (\texttt{algoritmoRandom} y \\ \texttt{algoritmoRandomOptimizado} de manera de ver la mejora realizada respecto a la cantidad de movimientos realizados sobre los resultados obtenidos del primero.

\begin{figure}[here]
\begin{tikzpicture}
\begin{axis}[
x tick label style={
/pgf/number format/1000 sep=},
ylabel=Movimientos,
enlargelimits=0.10,
legend style={at={(0.5,-0.15)},
anchor=north,legend columns=-1},
ybar,
bar width=7pt,
nodes near coords,
]

\addplot
coordinates {(1,88) (2,73)
(3,87) (4,107) (5,85)};

\addplot
coordinates {(1,82) (2,68)
(3,81) (4,102) (5,81)};

\legend{Random,Random Optimizado}
\end{axis}
\end{tikzpicture}
\caption{Distintas ejecuciones del algoritmo ``Random Optimizado'', tomando como distribucion inicial la de ``prueba10.txt'', mostrando la reduccion de movimientos de autos que se logra en cada ejecucion.}
\label{RandomPrueba10}
\end{figure}

\vspace{5 mm}

\begin{figure}[here]
\begin{tikzpicture}
\begin{axis}[
x tick label style={
/pgf/number format/1000 sep=},
ylabel=Movimientos,
enlargelimits=0.10,
legend style={at={(0.5,-0.15)},
anchor=north,legend columns=-1},
ybar,
bar width=7pt,
nodes near coords,
]

\addplot
coordinates {(1,186) (2,174)
(3,183) (4,172) (5,178)};

\addplot
coordinates {(1,180) (2,168)
(3,183) (4,166) (5,172)};

\legend{Random,Random Optimizado}
\end{axis}
\end{tikzpicture}
\caption{Distintas ejecuciones del algoritmo ``Random Optimizado'', tomando como distribucion inicial la de ``prueba20.txt'', mostrando la reduccion de movimientos de autos que se logra en cada ejecucion.}
\label{RandomPrueba20}
\end{figure}

\vspace{2 mm}

\begin{figure}[here]
\begin{tikzpicture}
\begin{axis}[
x tick label style={
/pgf/number format/1000 sep=},
ylabel=Movimientos,
enlargelimits=0.10,
legend style={at={(0.5,-0.15)},
anchor=north,legend columns=-1},
ybar,
bar width=7pt,
nodes near coords,
]

\addplot
coordinates {(1,258) (2,325)
(3,239) (4,211) (5,149)};

\addplot
coordinates {(1,171) (2,234)
(3,191) (4,169) (5,133)};

\legend{Random,Random Optimizado}
\end{axis}
\end{tikzpicture}
\caption{Distintas ejecuciones del algoritmo ``Random Optimizado'', tomando como distribucion inicial la de ``prueba5.txt'', mostrando la reduccion de movimientos de autos que se logra en cada ejecucion.}
\label{RandomPrueba5}
\end{figure}


\begin{figure}[here]
\begin{tikzpicture}
\begin{axis}[
x tick label style={
/pgf/number format/1000 sep=},
ylabel=Movimientos,
enlargelimits=0.10,
legend style={at={(0.5,-0.15)},
anchor=north,legend columns=-1},
ybar,
bar width=7pt,
nodes near coords,
]

\addplot
coordinates {(1,115) (2,111)
(3,175) (4,188) (5,174)};

\addplot
coordinates {(1,114) (2,98)
(3,134) (4,141) (5,124)};

\legend{Random,Random Optimizado}
\end{axis}
\end{tikzpicture}
\caption{Distintas ejecuciones del algoritmo ``Random Optimizado'', tomando como distribucion inicial la de ``prueba3.txt'', mostrando la reduccion de movimientos de autos que se logra en cada ejecucion.}
\label{RandomPrueba3}
\end{figure}


\clearpage

\section{Discusi\'on}
Analizaremos a continuaci\'on los resultados obtenidos en los experimentos mostrados en la secci\'on anterior.

\subsection*{Experimento 1}
El prop\'osito de este experimento es comparar la cantidad de movimientos de veh\'iculos que se deben efectuar en un edificio para que el mismo no colapse cuando llegue el terremoto. Los algoritmos de reubicaci\'on que se utilizan en este experimento son todos determin\'isticos, a diferencia de los no determin\'isticos que se discutir\'an en los pr\'oximos experimentos. 

Se plantean cinco casos, donde en cada uno lo que var\'ia es la cantidad de pisos que tiene el edificio. Veremos que uno de los tres algoritmos determin\'isticos logra encontrar un plan de reubicaci\'on exitoso para el primer caso, mientras que para los restantes no lo encuentra. Adem\'as seleccionaremos aquel algoritmo que realiza el plan de reubicaci\'on minimizando la cantidad de movimientos de veh\'iculos.

\subsubsection*{a) Edificio de 3 pisos, de masa total igual a 934500.}
Para esta etapa del experimento, se utiliz\'o el archivo de prueba \texttt{prueba3.txt}, el cual contiene las caracter\'isticas de un edificio de 3 pisos: su masa, la masa de los veh\'iculos livianos y pesados, los coeficientes de rigidez, la cantidad de autos livianos y pesados por piso, y la cantidad total de pisos del edificio.

Como se ve en la Figura \ref{determ3}, los tres algoritmos toman casi la misma cantidad de movimientos, pero el que minimiza esta cantidad es el \texttt{algoritmoMedalla}. El \texttt{algoritmoIntuicion} encuentra una soluci\'on exitosa para este caso, pero de todas formas lo hace usando mayor cantidad de movimientos que los otros dos m\'etodos.

\subsubsection*{b) Edificio de 5 pisos, de masa total igual a 632500.}
En esta etapa se us\'o el archivo \texttt{prueba5.txt}, el cual simula un edificio de 5 pisos.

Nuevamente, a partir de la Figura \ref{determ5}, observamos que el \texttt{algoritmoMedalla} reubica los autos de manera m\'as eficiente que el \texttt{algoritmoMedallaLazy}: el primero realiza 99 movimientos, mientras que el segundo 103. Por otro lado, notamos que no hay barra graficada para el \texttt{algoritmoIntuicion}, ya que al correr el programa con este algoritmo y este archivo de prueba, se informa al usuario que no se ha encontrado un plan de reubicaci\'on que logre evitar que el edificio colapse. ?`Por qu\'e ocurre esto?

Como se explic\'o en la secci\'on Desarrollo, el \texttt{algoritmoIntuicion} selecciona un piso que est\'a en conflicto (el que tiene una frecuencia en el rango $(2.7;3.3)$) y, en caso de que todav\'ia queden autos en ese piso, se env\'ia uno de alg\'un tipo al piso ``m\'as resistente'', es decir, aqu\'el cuya frecuencia est\'a m\'as alejada del rango conflictivo. El problema aparece cuando el piso que est\'a en problemas ya no tiene m\'as autos: como el piso en conflicto no tiene m\'as autos para enviar a otro piso, el algoritmo se estanca y no sabe qu\'e hacer. Es por esto que el \texttt{algoritmoIntuicion} no es tan eficiente y no se garantiza que siempre encuentre una soluci\'on.

\subsubsection*{c) Edificio de 6 pisos, de masa total igual a 632500.}
Ahora analizaremos un edificio de 6 pisos (archivo \texttt{prueba6.txt}).

Como viene ocurriendo, el \texttt{algoritmoMedalla} parece ser el mejor en t\'erminos de cantidad de movimientos. Nuevamente, este m\'etodo vuelve a tomar menos cantidad de movimientos que el \texttt{algoritmoMedallaLazy} (ver Figura \ref{determ6}), y para el \texttt{algoritmoIntuicion} no hay barra graficada, ya que otra vez este algoritmo no encuentra soluci\'on para la reubicaci\'on de los autos. 
 

\subsubsection*{d) Edificio de 10 pisos, de masa total igual a 281200.}
En este caso tenemos un edificio de 10 pisos (archivo \texttt{prueba10.txt}).

Como vemos en la Figura \ref{determ10}, el \texttt{algoritmoMedalla} toma 19 movimientos, en cambio el \texttt{algoritmoMedallaLazy} toma un movimiento m\'as. Adem\'as observamos que esta cantidad ha bajado dr\'asticamente respecto de los tres casos anteriores; sin embargo, veremos luego que \textbf{no} es verdad que a menor masa total del edificio, menor es la cantidad de movimientos que hay que hacer para evitar que colapse. 

El \texttt{algoritmoIntuicion} no encuentra soluci\'on, como en los dos casos anteriores. 


\subsubsection*{e) Edificio de 20 pisos, de masa total igual a 574000.}
Para este \'ultimo caso se tom\'o un edificio de 20 pisos (archivo \texttt{prueba20.txt}).

A partir de la Figura \ref{determ20}, vemos que el \texttt{algoritmoMedalla} realiza menos movimientos que el \texttt{algoritmoMedallaLazy} (alrededor de un 20\% menos de movimientos), y que nuevamente no hay barra graficada para el \texttt{algoritmoIntuicion}.

\vspace{10 mm}

Para concluir, destaquemos algunos puntos:

\begin{itemize}
\item El \texttt{algoritmoIntuicion} no es totalmente infalible. Hemos visto que, de las 5 pruebas que hicimos, s\'olo para una de ellas encontr\'o una soluci\'on (para el primer caso). Y aunque vemos que funciona en el caso donde el edificio tiene pocos pisos (3), si vamos alterando su distribuci\'on inicial (masa, cantidad de autos livianos y pesados, etc) y corriendo el algoritmo, vemos que hay veces en que encuentra soluci\'on y veces en las que no. Del mismo modo, si tomamos un edificio de 10 pisos por ejemplo, como el caso d), en el cual el algoritmo falla, y modificamos algunos de sus datos iniciales, observaremos que para algunas distribuciones el algoritmo encuentra la soluci\'on. Luego, no podemos decir que el \texttt{algoritmoIntuicion} falla siempre o funciona siempre, o a veces, o nunca. Su \'exito depende mucho de la distribuci\'on inicial del edificio, irrespectivamente de la cantidad de pisos que posea, su masa total, las constantes de rigidez, etc.

\item No es cierto tampoco que si un edificio tiene masa $x$ y otro tiene masa $y$ (donde $y>x$), entonces el de masa $y$ requiere mayor n\'umero de movimientos de autos. Por ejemplo, tomemos el \texttt{algoritmoMedalla}. Para el edificio de 10 pisos, que tiene una masa menor que el de 20 pisos, la cantidad de movimientos que requiere es 19, mientras que para el segundo edificio es 64. Sin embargo, para los edificios de 3 y de 5 pisos, donde la masa del de 3 es mayor que el de 5 pisos, se requieren 74 movimientos para el edificio de 3 pisos y 99 para el de 5 pisos. Aqu\'i la relaci\'on \textit{masa total/cantidad de movimientos} es proporcionalmente inversa, mientras que para los edificios de 10 y de 20 pisos, la relaci\'on es directa. Entonces concluimos que la cantidad de movimientos no depende de las masas totales de los edificios.

\item Claramente, de los tres algoritmos determin\'isticos, el m\'as eficiente es el \texttt{algoritmoMedalla}, ya que siempre toma menor cantidad de movimientos que los otros dos y, como se discuti\'o en la secci\'on Desarrollo, es un m\'etodo m\'as exhaustivo que los otros dos, a costa de ser el m\'as lento.
\end{itemize}




\subsection*{Experimento 2}

El prop\'osito de este experimento es analizar c\'omo el \texttt{algoritmoRandomOptimizado} mejora la distribuci\'on obtenida al azar del \texttt{algoritmoRandom}. Se plantean 4 gr\'aficos en donde cada uno muestra distintos resultados obtenidos en distintas ejecuciones con el mismo edificio como input. En todos los gr\'aficos vemos c\'omo siempre el n\'umero de movimientos de autos se redujo despu\'es de haber realizado la optimizaci\'on. Por un lado, vemos c\'omo en las figuras \ref{RandomPrueba20} y \ref{RandomPrueba10} la mejora que realiza es muy leve (en promedio, reduce la cantidad de movimientos en 5). Pero mirando las figuras \ref{RandomPrueba5} y \ref{RandomPrueba3} vemos c\'omo se reduce notablemente la cantidad de movimientos de autos una vez hecha la optimizaci\'on. Una causa que podr\'iamos deducir de esto es que con una proporci\'on baja de autos por pisos (claro ejemplo de los archivos de pruebas prueba10.txt y prueba20.txt) la mejora en la cantidad de movimientos es leve, mientras que si la proporci\'on de autos por pisos es mayor (archivos de pruebas 3 y 5) la reducci\'on en la cantidad de movimientos es mucho m\'as grande.

\begin{center}
\line(1,0){438}
\end{center}

\vspace{10mm}

En esta secci\'on se han realizado experimentos con tres algoritmos determin\'isticos y dos no determin\'isticos para reubicar los veh\'iculos de un edificio para evitar que \'este colapse cuando llegue el terremoto.

De los tres determin\'isticos, vimos en el Experimento 1 que el \texttt{algoritmoMedalla} le sacaba ventaja a los algoritmos \texttt{MedallaLazy} e \texttt{Intuicion}, y que, de los algoritmos no determin\'isticos (Experimento 2), el m\'as eficiente resultaba ser el \texttt{algoritmoRandomOptimizado}. Luego, si tenemos que seleccionar un m\'etodo de los cinco, elegimos el \texttt{Medalla}, ya que minimiza la cantidad de movimientos en cualquiera de los escenarios analizados.




\newpage

\section{Conclusiones}

Como conclusi\'on de este trabajo, podemos destacar algunos puntos:

\begin{enumerate}
\item El algoritmo QR es \'util si se desea hallar los autovalores de una matriz dada. Si \'esta es esparsa, entonces el algoritmo usa la factorizaci\'on QR de cada una de las matrices en la sucesi\'on utilizando el m\'etodo de Givens. Este \'ultimo m\'etodo aprovecha que la matriz a factorizar es esparsa, y entonces se evitan calcular muchas operaciones (se reduce dr\'asticamente el n\'umero de matrices de rotaci\'on a usar). El m\'etodo de Givens, luego, supera al de HouseHolder en cuanto a facilidad en su implementaci\'on y en optimizaci\'on de operaciones.  
\item De los cinco algoritmos de reubicaci\'on de veh\'iculos, podemos afirmar, luego de haber analizado todos los gr\'aficos de la secci\'on Resultados, que los mejores son \texttt{algoritmoMedalla} y \texttt{algoritmoMedallaLazy}. En cuanto a tiempo de ejecuci\'on, es cierto que el \texttt{algoritmoMedalla} es m\'as lento que el \texttt{algoritmoMedallaLazy}, pero realiza menos movimientos que el \texttt{Lazy}. Es por ello que conclu\'imos que el algoritmo que optimiza la cantidad de movimientos es el \texttt{Medalla}. 
\end{enumerate}

Como experimentos pendientes, podemos nombrar \'este: tomar un edificio de $n$ pisos y analizar c\'omo cambian las frecuencias de los pisos a medida que aumentamos la proporci\'on de autos por piso. Tal vez haciendo esto se encuentra un patr\'on en el cambio de las frecuencias; por ejemplo, que a medida que se incrementa la cantidad de autos por piso, se incrementen las frecuencias de los pisos.


\newpage

\section{Ap\'endices}

\subsection*{Ap\'endice A}

\begin{center}
\bf Laboratorio de M\'etodos Num\'ericos - Primer cuatrimestre 2012 \\[5pt]
\bf Trabajo Pr\'actico N\'umero 3 %Cuando pase el temblor ... \\
\end{center}

\vskip 25pt
\hrule
\vskip 11pt

El trabajo pr\'actico consiste en evaluar la resistencia s\'\i smica de un
edificio de varios pisos que funciona como estacionamiento, proponiendo un plan de
reubicaci\'on de los veh\'iculos lo m\'as eficiente posible.

%\begin{figure}[h]
%\centering
%\includegraphics[height=0.25\textheight]{figura1.eps}
%\caption{Modelo del edificio}
%\end{figure}

\textbf{El modelo}

Consideremos un edificio de $n$ pisos como el de la Figura~1. Un modelo sencillo
para estudiar el efecto de un terremoto sobre el edificio consiste en
considerar cada piso $i=1,\dots,n$ como un bloque de masa $m_i$, unido a los
pisos adyacentes por medio de un conector el\'astico cuya acci\'on se parece
a la de un resorte. Para $i=0,\dots,n-1$, la uni\'on entre los pisos $i$ e
$i+1$ suministra una fuerza de restituci\'on
\begin{displaymath}
F_i\ =\ k_i (x_{i+1}-x_i),
\end{displaymath}
donde $x_i(t)\colon \mathbb{R}_+ \rightarrow \mathbb{R}$ representa el desplazamiento
horizontal del $i$-\'esimo piso en cada instante con respecto al suelo (asumimos que $i=0$ corresponde
al suelo y que $x_0=0$), y los $k_i\in\mathbb{R}_+$ representan los coeficientes
de rigidez. Aplicando la segunda ley de Newton del movimiento %$F = ma$ 
a cada secci\'on del edificio ($m_i\, a_i = F_i-F_{i-1}$, con $a_i$ la aceleraci\'on, que escribiremos como la derivada segunda de $x_i$), 
obtenemos el siguiente sistema de ecuaciones diferenciales ordinarias:
\begin{eqnarray*}
m_1 \ddot{x}_1 & = & -k_0 x_1 + k_1 (x_2-x_1) \nonumber \\
m_2 \ddot{x}_2 & = & -k_1 (x_2-x_1) + k_2 (x_3-x_2) \nonumber \\
m_3 \ddot{x}_3 & = & -k_2 (x_3-x_2) + k_3 (x_4-x_3) \nonumber \\
\vdots &  & \vdots \nonumber \\
m_n \ddot{x}_n & = & -k_{n-1} (x_n-x_{n-1}) \nonumber \\
\end{eqnarray*}
Escrito en forma matricial, este
sistema toma la forma $M\ddot{\mathbf{x}} = K\mathbf{x}$, 
donde $M\in\mathbb{R}^{n\times n}$ es una matriz
diagonal con las masas de los pisos y $K\in\mathbb{R}^{n\times n}$ es una matriz
tridiagonal con los coeficientes de rigidez adecuados. Como $m_i>0$ para
$i=1,\dots,n$, entonces $M$ tiene inversa y el sistema se puede reescribir
como $\ddot{\mathbf{x}} = (M^{-1} K) \mathbf{x} = A\mathbf{x}$, donde $A = M^{-1} K$ tiene autovalores negativos.

Sean $\lambda_1,\dots,\lambda_n$ los autovalores de $A$. Los valores
$\omega_i=\sqrt{-\lambda_i}$, para $i=1,\dots,n$, representan las frecuencias
naturales del sistema, e indican la estabilidad del edificio durante un
terremoto. Si la frecuencia del sismo es muy pr\'oxima a alguna de estas
frecuencias, hay riesgo de que el edificio entre en resonancia y colapse.

\textbf{El problema}

Nos encontramos en el 
estacionamiento de una importante concesionaria de autom\' oviles de una reconocida marca,
% dep\'osito de lavarropas de una conocida casa de electrodom\'esticos, 
y se avecina un terremoto sobre nuestra ciudad. 
Contamos con informaci\'on fidedigna provista por nuestro
informante en el Departamento de Geolog\'\i a de la FCEyN 
de que la frecuencia del terremoto ser\'a $\omega = 3\ \hbox{Hz}
= 3 \frac{1}{\hbox{seg}}$.

Para realizar c\'alculos simplificados podemos asumir que todos los autos 
se pueden agrupar en 2 categor\'ias: livianos, de masa $m_l$, y pesados, 
de masa $m_p > m_l$.
Adem\'as, $m_0$ es la masa propia del edificio correspondiente a cada piso.
De esta forma, si el piso $i$ tiene $l_i$ veh\'\i culos livianos y 
$p_i$ veh\'\i culos pesados, entonces su masa es $m_i = m_0 + l_i m_l + p_i m_p$. 
El problema que debemos resolver -y r\'apidamente- consiste en determinar
cu\'antos autos livianos y pesados debemos quitar de cada piso 
(reubic\'andolos en otros pisos) para que ninguna de las frecuencias 
naturales del edificio se encuentre a menos del 10\% de la frecuencia 
$\omega$ del terremoto.
La soluci\'on \'optima del problema es aquella que permite evitar que el
edificio colapse, reubicando la menor cantidad posible de autom\'oviles.

\textbf{El enunciado}

El trabajo pr\'actico consiste en implementar un programa que permita 
resolver este problema. La soluci\'on propuesta debe indicar cu\'antos 
autos livianos y cu\'antos pesados quitar de cada piso, y a qu\'e pisos 
se deben llevarlos. 

Deben proponerse (por lo menos) dos m\'etodos (es v\'alido que sean 
heur\'\i sticos) para obtener el plan de reubicaci\'on. El informe 
deber\'a contener los resultados de los experimentos realizados para
compararlos y evaluar cu\'al es mejor. 

El programa debe incluir una implementaci\'on de
alg\'un algoritmo para calcular los autovalores de una matriz cuadrada, que
deber\'a ser utilizado durante el proceso de decisi\'on. Sugerimos implementar
el algoritmo QR para el c\'alculo de autovalores. El programa debe tomar los
datos desde un archivo de texto con el siguiente formato:
\begin{eqnarray}
 & & n\ m_0\ m_l\ m_p \nonumber \\
 & & k_0\ k_1\ \dots\ k_{n-1} \nonumber \\
 & & l_1\ l_2\ \dots\ l_n \nonumber \\
 & & p_1\ p_2\ \dots\ p_n \nonumber
\end{eqnarray}
Se debe retornar la soluci\'on propuesta con este mismo formato.

El programa que obtenga la mejor redistribuci\'on de autom\'oviles se har\'a
acreedor a la medalla \emph{M\'etodos Num\'ericos 2012} al Mejor Redistribuidor Vehicular.

\vskip 15pt

\hrule

\vskip 11pt


{\bf \underline{Entrega Final}}
\vspace{-15pt}
\begin{description}
  \setlength{\itemsep}{0pt}
  \setlength{\parskip}{0pt}
  \setlength{\parsep}{0pt}
 \item[Formato Electr\'onico:] jueves 28 de junio de 2012, hasta las 23:59 hs, a la direcci\'on: 

  {\emph{metnum.lab@gmail.com}}
%  \item[Formato f\'isico y experimentaci�n en clase:] 13 de abril de 2012, de 17 a 21 hs.
 \item[Formato f\'isico:] viernes 29 de junio de 2012, de 17 a 19 hs.
 \item[Competencia entre grupos:] viernes 29 de junio de 2012, 19 hs.
 \item[Entrega de premios:] viernes 29 de junio de 2012, 20:30 hs.
\end{description}

\newpage

\subsection*{Ap\'endice B}
A continuaci\'on se provee el c\'odigo fuente de las funciones m\'as relevantes desde el punto de vista num\'erico. \'Estas son: factQR, algoritmoQR, algoritmoMedalla, algoritmoMedallaLazy, algoritmoRandomOptimizado, algoritmoIntuicion, algoritmoRandom.

\begin{verbatim}
void factQR(double* A, int n, double* Q, double* R)
{
    double* P = new double[n*n];
    double* RES = new double[n*n];
    double* RESQ = new double[n*n];
    double norm_actual;
    double x1;
    double x2;

    llenarConLaIdentidad(Q,n);

    int indice2;
    int indice1;

    for(int p = 1;p<n;p++)
    {
        indice1 = (p-1)*n+(p-1);
        indice2 = (p-1)*n+(p-1)+n;
        x1 = A[indice1];
        x2 = A[indice2];
        norm_actual = sqrt(x1*x1+x2*x2);

        llenarConLaIdentidad(P,n);

        P[indice1] = x1/norm_actual;
        P[indice1+1] = x2/norm_actual;
        P[indice2] = -x2/norm_actual;
        P[indice2+1] = x1/norm_actual;

        multiplicar(P,Q,n,n,n,RESQ);
        multiplicar(P,A,n,n,n,RES);

        for(int i=0; i<n*n; i++)
        {
            A[i] = RES[i];
            Q[i] = RESQ[i];
        }
    }

    trasponer(Q,n,n,RESQ);

    for(int i=0; i<n*n; i++)
    {
        Q[i] = RESQ[i];
        R[i] = A[i];
    }

    delete [] P;
    delete [] RES;
    delete [] RESQ;

}

void algoritmoQR(double* A, int n, double* D)
{
    double* Q = new double[n*n];
    double* R = new double[n*n];
    int iteraciones = 0;
    int maxIter = 1000;
    double tol = 0.1;
    double normaUno = 0;

    normaUno = normaUnoMatrizInf(A,n);

    while(normaUno > tol && iteraciones < maxIter)
    {
        factQR(A,n,Q,R);
        multiplicar(R,Q,n,n,n,A);

        iteraciones++;
        normaUno = normaUnoMatrizInf(A,n);

    }

    for(int i=0; i<n; i++)
    {
        D[i] = A[i*n+i];
    }

    delete [] Q;
    delete [] R;
}

int algoritmoMedalla(double * M,double * K, double * autovalores, int n)
{
    double * A = new double[n*n];
    double * w = new double[n];
    bool pisosObsoletos[n][n];
    double dif;
    double ant;
    double freqactual = -1;
    int pisoactual, pisoanterior, pisoOrigen, pisoDestino,tipo;
    double difMax;
    int cantMov = 0;

    do
    {
        difMax = 0;
        pisoactual = -1;
        armarM(M,n);
        multiplicar(M,K,n,n,n,A);
        algoritmoQR(A,n,autovalores);
        for(int i=0; i < n; i++)
        {
            freqactual = sqrt( (-1) * autovalores[i] );
            if(freqactual < 3.3 && freqactual > 2.7 )
            {
                pisoanterior = pisoactual;
                pisoactual = i;
				//me guardo el piso que esta en conflicto y salgo del "for"
                
                break;
            }
        }

        if(pisoactual != -1)
        {

            if(pisoactual != pisoanterior)
            {
                    for(int j = 0; j<n;j++)
                    {
                        for(int i = 0;i<n;i++)
                        {
                            pisosObsoletos[j][i] = 0;
                            if(j == i)
                            {
                                pisosObsoletos[j][i] = 1;
                            }
                        }
                    }
            }
            for(int i = 0;i < n;i++)
            {
                for(int j = 0; j < n;j++)
                {
                    if(pisosObsoletos[i][j] == 0)
                    {
                        if(p[i] > 0)//Si hay autos..
                        {
                            p[i]--;
                            p[j]++;
                            //calculo cuanto me da este traslado
                            armarM(M,n);

                            multiplicar(M,K,n,n,n,A);

                            algoritmoQR(A,n,autovalores);


                            if(freqactual < 3)
							//si la frequencia era menor que 3, me conviene buscar una
							//frecuencia menor ya que estoy mas cerca de 2.7 que de 3.3
                            {
                                dif =  freqactual - 
							          	sqrt( (-1) * autovalores[pisoactual] );

                                if(dif > 0)
                                {
                                    if(dif > difMax)
                                    {
                                        difMax = dif;
                                        pisoOrigen = i;
                                        pisoDestino = j;
                                        tipo = 1;
                                    }
                                }
                                else
                                {
                                    pisosObsoletos[i][j] = 1;
                                }
                            }
                            else
                            {
                                dif = sqrt( (-1) * 
								      autovalores[pisoactual] ) - freqactual;

                                if(dif > 0)
                                {
                                    if(dif > difMax)
                                    {
                                        difMax = dif;
                                        pisoOrigen = i;
                                        pisoDestino = j;
                                        tipo = 1;
                                    }
                                }
                                else
                                {
                                    pisosObsoletos[i][j] = 1;
                                }
                            }

                            p[i]++;
                            p[j]--;
                        }
                        if(l[i] > 0)
                        {
                            l[i]--;
                            l[j]++;

                            armarM(M,n);
                            multiplicar(M,K,n,n,n,A);
                            algoritmoQR(A,n,autovalores);

                            if(freqactual < 3)
                            {
                                dif =  freqactual - sqrt( (-1) * 
								       autovalores[pisoactual] );


                                if(dif > 0)
                                {
                                    if(dif > difMax)
                                    {
                                        difMax = dif;
                                        pisoOrigen = i;
                                        pisoDestino = j;
                                        tipo = 0;
                                    }
                                }
                                else
                                {
                                    pisosObsoletos[i][j] = 1;
                                }
                            }
                            else
                            {
                                dif = sqrt( (-1) * 
							        	autovalores[pisoactual] ) - freqactual;
                                if(dif > 0)
                                {
                                    if(dif > difMax)
                                    {
                                        difMax = dif;
                                        pisoOrigen = i;
                                        pisoDestino = j;
                                        tipo = 0;
                                    }
                                }
                                else
                                {
                                    pisosObsoletos[i][j] = 1;
                                }
                            }

                            l[i]++;
                            l[j]--;
                        }
                    }
                }
            }
           
            if(tipo == 0)
            {
                l[pisoOrigen]--;
                l[pisoDestino]++;
                cantMov++;
            }
            else
            {
                p[pisoOrigen]--;
                p[pisoDestino]++;
                cantMov++;
            }
        }
    }while(pisoactual != -1);

    delete [] A;
    delete [] w;

    return cantMov;

}

int algoritmoMedallaLazy(double * M,double * K, double * autovalores, int n)
{
    double * A = new double[n*n];
    double * w = new double[n];
    bool pisosObsoletos[n][n];
    double dif;
    double ant;
    double freqactual = -1;
    int pisoanterior,pisoactual, pisoOrigen, pisoOrigenAnterior, 
	pisoDestino, pisoDestinoAnterior, tipo, tipoAnterior;
    double difMax;
    int cantMov = 0;
    bool hayAutosTodavia=0;
    int o = 1;

    do
    {
        difMax = 0;
        pisoanterior = pisoactual;
        pisoactual = -1;
        armarM(M,n);
        multiplicar(M,K,n,n,n,A);
        algoritmoQR(A,n,autovalores);
        for(int i=0; i < n; i++)
        {
            freqactual = sqrt( (-1) * autovalores[i] );
            if(freqactual < 3.3 && freqactual > 2.7 )
            {
                pisoactual = i;
				//me guardo el piso que esta en conflicto y salgo del "for"
                
                break;
            }
        }

        if(pisoactual != -1)
        {
            hayAutosTodavia = 0;
            if(tipoAnterior == 1)
            {
                if(o != 1 && p[pisoOrigenAnterior] > 0)
                {
                    hayAutosTodavia = 1;
                }
            }
            else
            {
                if(o != 1 && l[pisoOrigenAnterior] > 0)
                {
                    hayAutosTodavia = 1;
                }
            }

            if(pisoactual != pisoanterior)
            {
                    for(int j = 0; j<n;j++)
                    {
                        for(int i = 0;i<n;i++)
                        {
                            pisosObsoletos[j][i] = 0;
                            if(j == i)
                            {
                                pisosObsoletos[j][i] = 1;
                            }
                        }
                    }
            }

            if(o != 1 && pisoanterior == pisoactual && hayAutosTodavia)
            {

                pisoOrigen=pisoOrigenAnterior;
                pisoDestino=pisoDestinoAnterior;
                tipo=tipoAnterior;
                
            }
            else
            {
                for(int i = 0;i < n;i++)
                {
                    for(int j = 0; j < n;j++)
                    {
                        if(pisosObsoletos[i][j] == 0)
                        {
                            
                            if(p[i] > 0)//Si hay autos..
                            {
                                p[i]--;
                                p[j]++;
                                //calculo cuanto me da este traslado
                                armarM(M,n);
                              
                                multiplicar(M,K,n,n,n,A);
                               
                                algoritmoQR(A,n,autovalores);
                              

                                if(freqactual < 3)
								//si la frequencia era menor que 3, 
								//me conviene buscar una frecuencia menor ya que estoy mas
								//cerca de 2.7 que de 3.3
                                {
                                    dif =  freqactual - 
									     sqrt( (-1) * autovalores[pisoactual] );

                                    if(dif > 0)
                                    {
                                        if(dif > difMax)
                                        {
                                            difMax = dif;
                                            pisoOrigen = i;
                                            pisoDestino = j;
                                            tipo = 1;
                                        }
                                    }
                                    else
                                    {
                                        pisosObsoletos[i][j] = 1;
                                    }
                                }
                                else
                                {
                                    dif = sqrt( (-1) * 
								        	autovalores[pisoactual] ) - freqactual;

                                    if(dif > 0)
                                    {
                                        if(dif > difMax)
                                        {
                                            difMax = dif;
                                            pisoOrigen = i;
                                            pisoDestino = j;
                                            tipo = 1;
                                        }
                                    }
                                    else
                                    {
                                        pisosObsoletos[i][j] = 1;
                                    }
                                }

                                p[i]++;
                                p[j]--;
                            }
                            if(l[i] > 0)
                            {
                                l[i]--;
                                l[j]++;

                                armarM(M,n);
                                
                                multiplicar(M,K,n,n,n,A);
                               
                                algoritmoQR(A,n,autovalores);
                              

                                if(freqactual < 3)
                                {
                                    dif =  freqactual - 
									      sqrt( (-1) * autovalores[pisoactual] );


                                    if(dif > 0)
                                    {
                                        if(dif > difMax)
                                        {
                                            difMax = dif;
                                            pisoOrigen = i;
                                            pisoDestino = j;
                                            tipo = 0;
                                        }

                                    }
                                    else
                                    {
                                        pisosObsoletos[i][j] = 1;
                                    }
                                }
                                else
                                {
                                    dif = sqrt( (-1) * 
									    autovalores[pisoactual] ) - freqactual;
                                    if(dif > 0)
                                    {
                                        if(dif > difMax)
                                        {
                                            difMax = dif;
                                            pisoOrigen = i;
                                            pisoDestino = j;
                                            tipo = 0;
                                        }
                                    }
                                    else
                                    {
                                        pisosObsoletos[i][j] = 1;
                                    }
                                }

                                l[i]++;
                                l[j]--;
                            }
                        }
                    }
                }
            }
        }
        
        pisoOrigenAnterior = pisoOrigen;
        pisoDestinoAnterior = pisoDestino;
        tipoAnterior = tipo;
        o++;
        if(tipo == 0)
        {
            l[pisoOrigen]--;
            l[pisoDestino]++;
            cantMov++;
        }
        else
        {
            p[pisoOrigen]--;
            p[pisoDestino]++;
            cantMov++;
        }
    }while(pisoactual != -1);

    delete [] A;
    delete [] w;

    return cantMov;

}

int algoritmoRandomOptimizado(double * M,double * K, double * autovalores, int n)
{
    int cantMov=0;
    cantMov = algoritmoRandom(M,K,n);
    bool pisosListos[n];
    bool faltanPisos = 1;
    int pisoARevisar = 0;
    int pisoDestino,pisoPosibleConflicto;
    double dif, difMax,difMinAnterior;
    double * autovalores_orig = new double[n];
    double temp;
    bool pisosDestinos[n];
    double diferencias[n];
    double * A = new double[n*n];
    bool huboCambio = 1;

    armarM(M,n);
    multiplicar(M,K,n,n,n,A);
    algoritmoQR(A,n,autovalores_orig);

    while(huboCambio)
    {
        huboCambio = 0;
        obtenerDiferencias(M,K,autovalores,pisosDestinos,diferencias,n);
        while(true)
        {
            double difMayor = 0;
            int pisoOrigen = 0;
            int i;
            for(i = 0;i<n;i++)
            {
                if(diferencias[i] > difMayor)
                {
                    difMayor = diferencias[i];

                    pisoOrigen = i;
                }
            }
            if(difMayor == 0)
            {
                break;
            }
            pisoDestino=pisosDestinos[pisoOrigen];
            
            int h = 0;

            while(l_orig[pisoOrigen] < l[pisoOrigen] && 
			      l_orig[pisoDestino] > l[pisoDestino] && 
			      (h == 0 || !colapsa(autovalores,n)))
            {
                l[pisoDestino]++;
                l[pisoOrigen]--;
                armarM(M,n);
                multiplicar(M,K,n,n,n,A);
                algoritmoQR(A,n,autovalores);
                h++;
            }

            if(h > 0)
            {
                if(colapsa(autovalores,n))
                {
                    l[pisoDestino]--;
                    l[pisoOrigen]++;
                }
                if(h > 1)
                {
                    huboCambio = 1;

                }
            }

            diferencias[pisoOrigen] = 0;
        }
    }
    cantMov = cuentaMovimientos(n);

}

int algoritmoIntuicion(double * M,double * K, double * autovalores, int n)
{
    int cantMov = 0;
    double * A = new double[n*n];
    double * w = new double[n];
    int pisoOrigen;
    int pisoDestino;
    double temp,max;

    do
    {
        max=0;
        pisoOrigen = -1;
        for(int i=0; i < n; i++)
        {
            w[i] = sqrt( (-1) * autovalores[i] );
            cout << w[i] << '\t';
            if(w[i] < 3.3 && w[i] > 2.7 && (p[i] > 0 || l[i] > 0))
            {
                pisoOrigen = i;
            }
            else
            {
                temp = abs(w[i]-3.3);

                if(temp > max)
                {//Nuevo Candidato
                    pisoDestino = i;
                    max = temp;
                }
            }
        }
        cout << endl;
        if(pisoOrigen != -1)
        {
            if(p[pisoOrigen] > 0)
            {
                p[pisoOrigen]--;
                p[pisoDestino]++;
            }
            else
            {
                l[pisoOrigen]--;
                l[pisoDestino]++;
            }

        }
        else//¿No hay solucion?
        {
            cantMov = -1;
            break;
        }


        armarM(M,n);

        multiplicar(M,K,n,n,n,A);//Obtenemos A

        algoritmoQR(A,n,autovalores);
        cantMov++;
    }
    while(colapsa(autovalores,n));

    delete [] A;
    delete [] w;

    return cantMov;
}

int algoritmoRandom(double * M, double * K, int n)
{
    //ALGORITMO 1: Distribucion Al Azar
    int cantMov = 0;
    int total_l = 0,total_p = 0;
    int cant_autos;
    double * autovalores = new double[n];
    double * A = new double[n*n];
    srand ( time(NULL) );

    for(int i = 0;i<n;i++)
    {
        total_l = total_l + l[i];
        total_p = total_p + p[i];
    }

    do
    {
        int subtotal_l,subtotal_p;
        int piso;
        int tipo;
        subtotal_l = total_l;
        subtotal_p = total_p;
        bool pisos[n];
        int pisosAsignados = 0;

        for(int i = 0;i < n;i++)
        {
            pisos[i] = 0;
        }

        while(pisosAsignados < n && subtotal_l > 0)
        {
            cant_autos = rand() % subtotal_l;
            do
            {
                piso = rand() % n;
            }while(pisos[piso] == 1);
            l[piso] = cant_autos;
            pisos[piso] = 1;
            subtotal_l = subtotal_l - cant_autos;
            pisosAsignados++;
        
        }

        if(subtotal_l > 0)
        {
            //me quedaron autos sin asginar

            piso = rand() % n;
            l[piso] = l[piso] + subtotal_l;

        }


        for(int i = 0;i < n;i++)
        {
            pisos[i] = 0;
        }
        pisosAsignados = 0;
        while(pisosAsignados < n && subtotal_p > 0)
        {
            cant_autos = rand() % subtotal_p;
            piso = rand() % n;
            do
            {
                piso = rand() % n;
            }while(pisos[piso] == 1);

            p[piso] = cant_autos;
            pisos[piso] = 1;
            subtotal_p = subtotal_p - cant_autos;
            pisosAsignados++;

        }

        if(subtotal_p > 0)
        {
            //me quedaron autos sin asginar
            piso = rand() % n;

            p[piso] = p[piso] + subtotal_p;
        }

        armarM(M,n);

        multiplicar(M,K,n,n,n,A);//Obtenemos A

        algoritmoQR(A,n,autovalores);
        cantMov++;

    }
    while(colapsa(autovalores,n));

    cantMov = cuentaMovimientos(n);

    delete [] autovalores;

    delete [] A;


    return cantMov;
}

\end{verbatim}

\newpage

\section{Referencias}

A lo largo de la confecci\'on del trabajo pr\'actico, se consult\'o la siguiente bibliograf\'ia:

\begin{thebibliography}{99} 


\bibitem{Burden} Burden, Richard L. \& Faires, J. Douglas (1998). \textit{An\'alisis num\'erico, (6ta ed.)}

\bibitem{UniZ} Palacios, Manuel. Departamento de matem\'atica aplicada, Universidad de Zaragoza. \textit{Sistemas de ecuaciones lineales}. 

Adem\'as utilizamos varias herramientas que nos ayudaron para resolver el trabajo pr\'actico:

\bibitem{PGFP} \textit{PGFPlots Package}, paquete para realizar gr\'aficos en latex \\(http://pgfplots.sourceforge.net/).

\bibitem{Octave} \textit{GNU Octave 3.2.4.}, lenguaje de alto nivel, principalmente dedicado al an\'alisis num\'erico.



\end{thebibliography}

\end{document}

